package tianhao.luo.algorithm;

/**
 * 归并排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  20:39
 */
public class MergeSort {

    private int[] array;

    public MergeSort(int[] array) {
        this.array = array;
    }

    /**
     * 分+合并
     * @param left 最左边索引
     * @param right 最右边索引
     * @param temp 临时数组
     */
    public void mergeSort(int left,int right,int[] temp){

        if (left<right){
            // 中间索引
            int mid = (left+right)/2;
            // 向左递归进行分解
            mergeSort(left,mid,temp);
            // 向右递归进行分解
            mergeSort(mid+1,right,temp);

            // 分解到最后,才开始合并
            // 这是根据递归运行时,使用的栈的机制
            // 直到left和right相邻时,进入if判断内部方法,不再去递归了,才开始进行合并,依次向外
            merge(left,mid,right,temp);
        }

    }


    /**
     * 分而治之的合并方法
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    private void merge(int left,int mid,int right,int[] temp){
        // 左边有序序列的初始索引
        int i = left;
        // 右边有序序列的初始索引
        int j = mid+1;

        // 指向temp数组的当前索引
        int t = 0;

        // (一)
        // 先把左右两边(有序)的数据,按照规则填充到temp中,直到左右两边的有序序列,有一边处理完毕为止
        while (i<=mid && j<=right){
            // 如果左边有序序列的当前元素,小于等于右边有序序列的当前元素
            // 即将左边的当前元素,拷贝到temp数组
            // 然后t和i都需要后移
            if (array[i]<=array[j]){
                temp[t] = array[i];
                t++;
                i++;
            }else {
                // 如果右边有序序列的当前元素,小于左边有序序列的当前元素
                temp[t] = array[j];
                t++;
                j++;
            }
        }


        // (二)
        // 把有剩余数据的一边,依次填充到temp中
        // 左右两边,只会剩一边
        while (i<=mid){
            // 左边的有序序列有剩余的元素,就全部填充到temp中
            temp[t] = array[i];
            t++;
            i++;
        }
        while (j<=right){
            // 右边的有序序列有剩余的元素,就全部填充到temp中
            temp[t] = array[j];
            t++;
            j++;
        }


        // (三)
        // 将temp数组的元素,拷贝到array
        // 注意,并不是每一次都会拷贝所有
        t= 0;
        // 第一次合并 tempLeft = 0 ,right =1
        // 第二次合并 tempLeft = 2 ,right =3
        int tempLeft = left;
//        System.out.println("tempLeft="+tempLeft+" right="+right);
        while (tempLeft<=right){
            // 从temp拷贝回去
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }

    /**
     * 打印
     */
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}
